/**
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

 

示例 1：


输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true


*/


import java.util.*;
class Solution {
    public boolean exist(char[][] board, String word) {
        
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                boolean[][] visited=new boolean[board.length][board[0].length];
                if(dfs(board,word,visited,0,i,j)) return true;
            }
        }
       return false;

    }
    public boolean dfs(char[][]board,String c,boolean[][]visited,int k,int i,int j){
        if(board[i][j]!=c.charAt(k)){
            return false;
        }
        if(k==c.length()-1){
            return true;
        }
        
        boolean result=false;
        visited[i][j]=true;
        int[][] dirctions={{0,1},{0,-1},{1,0},{-1,0}};

        for(int[] dir: dirctions){
            int newi=i+dir[0];
            int newj=j+dir[1];
            if(newi>=0 && newi<board.length && newj>=0 &&newj<board[0].length){
                if(!visited[newi][newj]){
                    if(dfs(board,c,visited,k+1,newi,newj)){
                    result=true;
                    break;
                    }
                }
                
            }
        }
        visited[i][j]=false;
        return result;
    }
}